package day31_other;


import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName Solution
 * @Description 二分法
 * @Author clockTown
 * @Date 2021/6/9 19:13
 * @Version 1.0
 */
class Solution2 {
    public int solve(int[] nums) {
        int res = 0;
        //定义有序数组
        List<Integer> sortedNums = new ArrayList<>();
        //遍历原始数组nums
        for(int i = 0; i < nums.length; i++){
            //在排序数组中寻找满足条件的最左边界
            int leftBorder = findLeftBorder(sortedNums, nums[i] * 3);
            //在最左边界和i之间的数据都是满足题意的（因为已经一个一个排好序了）
            res += i - leftBorder;
            // 当前遍历的数据找到相应的排序下标
            int insertIndex = findLeftBorder(sortedNums, nums[i]);
            //将数据插入到原有排序数组中， 其中add方法为将原有的后移一位，新增的插入进去
            sortedNums.add(insertIndex, nums[i]);
        }
        return res;

    }
    private int findLeftBorder(List<Integer> sortedNums, int target){
        int left = 0, right = sortedNums.size() - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(sortedNums.get(mid) <= target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }
}

